package com.watson.onebox.algorithm;


import com.watson.onebox.proxy.CglibProxyIntercepter;
import com.watson.onebox.proxy.PersonService;
import org.springframework.cglib.core.DebuggingClassWriter;
import org.springframework.cglib.proxy.Enhancer;

import java.util.*;

public class Test {
    public static void main(String[] args) {


        //代理类class文件存入本地磁盘
        System.setProperty(DebuggingClassWriter.DEBUG_LOCATION_PROPERTY, "/Users/zhangpeng60/Downloads/workspace");
        Enhancer enhancer = new Enhancer();
        enhancer.setSuperclass(PersonService.class);
        enhancer.setCallback(new CglibProxyIntercepter());
        PersonService proxy = (PersonService) enhancer.create();
        proxy.setPerson();
        proxy.getPerson("1");

        Test test = new Test();
        boolean op = test.isPalindrome("OP");
        int[] src = {2, 3, 1, 2, 4, 3};
        int i = test.minSubArrayLen(7, src);
        int[] tmp = {-1, -1, -1, -1, -1, 0};
        int i1 = test.pivotIndex(tmp);
        String[] testargs = new String[2];
        testargs[0] = "ab";
        testargs[1] = "a";
//        testargs[2] = "fijl";
//        testargs[3] = "filkn";
        String s = test.test1(testargs);
        boolean valid = test.isValid("(){}}{");
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(1);
        listNode.next.next = new ListNode(1);
//       listNode.next.next.next = new ListNode(3);
//        listNode.next.next.next.next = new ListNode(3);
        ListNode listNode1 = test.test2(listNode);

        ListNode listNodeA = new ListNode(1);
        listNodeA.next = new ListNode(3);
        listNodeA.next.next = new ListNode(6);
        listNodeA.next.next.next = new ListNode(8);

        ListNode comm = new ListNode(9);
        comm.next = new ListNode(10);
        listNodeA.next.next.next.next = comm;

        ListNode listNodeB = new ListNode(12);
        listNodeB.next = new ListNode(32);
        listNodeB.next.next = new ListNode(61);
        listNodeB.next.next.next = new ListNode(81);
        listNodeB.next.next.next.next = comm;
        ListNode node = test.getIntersectionNode(listNodeA, listNodeB);


        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
        List<Integer> integers = test.spiralOrder(matrix);
        int[] tmp1 = {3, 5, 6, 2, 1, 7, 3, 9, 2};
        test.exchange(tmp1);

        ArrayList<String> ijfjsk = test.Permutation("ijfjsk");

        //[1,2,3,4,5,null,7,8]

        //           1
        //         /  \
        //        2    3
        //        / \    \
        //       4   5    7
        //      /
        //     8
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.left.left.left = new TreeNode(8);
        ListNode[] listNodes = test.listOfDepth(root);
        System.out.println(op);
    }

    public int minSubArrayLen(int s, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int sum = nums[0];
        int l = 0, r = 1;
        while (r < nums.length) {
            sum += nums[r];
            while (sum >= s) {
                minLen = Math.min(minLen, r - l + 1);
                sum -= nums[l];
                l++;
            }
            r++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    public int pivotIndex(int[] nums) {
        int l = 0, r = nums.length - 1;
        int suml = 0, sumr = 0;
        while (l < r) {
            if (suml < sumr && nums[l] > 0) {
                suml += nums[l++];
            } else {
                sumr += nums[r--];
            }
        }
        if (suml != sumr) l = -1;

        return l;
    }


    public boolean isPalindrome(String s) {
        int len = s.length();
        int r = len - 1;
        int i = 0;
        while (i < r) {
            int lc;
            if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                lc = s.charAt(i) - 'a';
            } else if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                lc = s.charAt(i) - 'A';
            } else {
                i++;
                continue;
            }
            int rc;
            if (s.charAt(r) >= 'a' && s.charAt(r) <= 'z') {
                rc = s.charAt(r) - 'a';
            } else if (s.charAt(r) >= 'A' && s.charAt(r) <= 'Z') {
                rc = s.charAt(r) - 'A';
            } else {
                r--;
                continue;
            }
            if (lc != rc) {
                return false;
            }
            i++;
            r--;
        }
        return true;
    }

    public String test1(String[] args) {
        int minLen = Integer.MAX_VALUE;
        for (String arg : args) {
            minLen = Math.min(arg.length(), minLen);
        }

        String ret = "";
        for (int i = 0; i < minLen; i++) {
            for (int j = 0; j < args.length; j++) {
                if (j == 0) {
                    ret = ret + args[j].charAt(i);
                } else if (args[j].charAt(i) == ret.charAt(i)) {
                    continue;
                } else {
                    return ret.isEmpty() ? ret : ret.substring(0, ret.length() - 1);
                }
            }
        }
        return ret;
    }

    public boolean isValid(String str) {
        if (str.isEmpty()) {
            return true;
        }
        List<Character> err = new ArrayList<>();
        err.add(')');
        err.add('}');
        err.add(']');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (stack.isEmpty()) {
                if (err.contains(str.charAt(i))) {
                    return false;
                }
                stack.push(str.charAt(i));
            } else {
                char c = stack.peek();
                if (getPing(str.charAt(i)) == c) {
                    stack.pop();
                } else {
                    if (err.contains(str.charAt(i))) {
                        return false;
                    }
                    stack.push(str.charAt(i));
                }
            }
        }
        return stack.isEmpty();
    }


    public char getPing(char ping) {
        switch (ping) {
            case '(':
                return ')';
            case ')':
                return '(';
            case '[':
                return ']';
            case ']':
                return '[';
            case '{':
                return '}';
            case '}':
                return '{';
            default:
                return 'e';
        }
    }

    //1,1,2,3,3

    public ListNode test2(ListNode head) {
        ListNode pre = head;
        ListNode cur = pre.next;
        while (cur != null) {
            if (pre.val == cur.val) {
                pre.next = cur.next;
            }
            pre = pre.next;
            if (pre != null) {
                cur = pre.next;
            } else {
                cur = null;
            }
        }
        return head;
    }

    public int[] etaat() {
        List<Integer> a = new ArrayList<>();
        a.toArray();
        return a.stream().mapToInt(i -> i).toArray();
    }

    public List<Integer> spiralOrder(int[][] matrix) {

        int max = matrix.length * matrix[0].length;
        List<Integer> ret = new ArrayList<>();
        int top = 0;
        int left = 0;
        int bottom = matrix.length - 1;
        int right = matrix[0].length - 1;

        while (max > 0) {

            for (int i = left; i <= right; i++) {
                ret.add(matrix[top][i]);
                max--;
            }
            top++;
            for (int i = top; i <= bottom; i++) {
                ret.add(matrix[i][right]);
                max--;
            }
            right--;
            for (int i = right; i >= left; i--) {
                ret.add(matrix[bottom][i]);
                max--;
            }
            bottom--;
            for (int i = bottom; i >= top; i--) {
                ret.add(matrix[i][left]);
                max--;
            }
            left++;
        }
        return ret;
    }

    /**
     *
     */
    public int[] exchange(int[] nums) {

        int len = nums.length;
        int right = len - 1;
        for (int i = 0; i < len && i < right; i++) {
            if (nums[i] % 2 == 0) {
                swap(nums, i, right--);
                i--;
            }
        }

        return nums;
    }

    //1,2,3,4,5,6
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode hA = headA;
        ListNode hB = headB;
        int lenA = 0;
        int lenB = 0;
        while (hA != null || hB != null) {
            if (hA != null) {
                lenA++;
                hA = hA.next;
            }
            if (hB != null) {
                lenB++;
                hB = hB.next;
            }
        }
        int sub = Math.abs(lenA - lenB);

        hA = headA;
        hB = headB;
        while (hA != null || hB != null) {
            if (sub != 0) {
                sub--;
                if (lenA > lenB) {
                    hA = hA.next;
                } else {
                    hB = hB.next;
                }
            } else if (hA == hB) {
                return hA;
            } else {
                hA = hA.next;
                hB = hB.next;
            }
        }
        return null;
    }


    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str == null || str.length() == 0)
            return list;
        char[] strArr = str.toCharArray();
        permu(list, strArr, 0);
        Collections.sort(list);
        return list;

    }

    private void permu(ArrayList<String> list, char[] strArr, int start) {

        // 递归终止条件
        if (start == strArr.length - 1) {
            String result = String.valueOf(strArr);
            // indexOf() 返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
            // 因为可能有字符重复，所以要做此判断
            if (list.indexOf(result) < 0) {
                list.add(result);
            }
        }
        for (int i = start; i < strArr.length; i++) {

            char temp = strArr[start];
            strArr[start] = strArr[i];
            strArr[i] = temp;

            permu(list, strArr, start + 1);

            temp = strArr[start];
            strArr[start] = strArr[i];
            strArr[i] = temp;
        }
    }

    public int[] singleNumbers(int[] nums) {
        int tmp = 0;
        int flag = 1;
        for (int n : nums) {
            tmp ^= n;
        }
        while ((flag & tmp) == 0) {
            flag <<= 1;
        }
        int num1 = tmp;
        int num2 = tmp;
        for (int n : nums) {
            if ((n & flag) == 0) {
                num1 ^= n;
            } else {
                num2 ^= n;
            }
        }
        int[] ret = new int[2];
        ret[0] = num1;
        ret[1] = num2;
        return ret;
    }

    public int maxLen(String s) {
        Set<Character> charSet = new HashSet<>();
        int left = 0, right = 0;
        int maxLen = 0;
        while (left <= right && (right < s.length())) {
            if (!charSet.contains(s.charAt(right))) {
                charSet.add(s.charAt(right));
                right++;
                maxLen = Math.max(maxLen, right - left);
            } else {
                charSet.remove(s.charAt(left));
                left++;
            }
        }

        return maxLen;
    }

    //abcabcbb
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
            dic.put(s.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }

    //[1,2,3,-1,-3,0,-1,0]
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> ret = new ArrayList<>();
        for (int first = 0; first < nums.length; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int third = nums.length - 1;
            int target = -nums[first];
            for (int second = first + 1; second < nums.length; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                while (second < third && nums[second] + nums[third] > target) third--;
                if (second == third) break;
                if (nums[second] + nums[third] == target) {
                    List<Integer> ele = new ArrayList<>();
                    ele.add(nums[first]);
                    ele.add(nums[second]);
                    ele.add(nums[third]);
                    ret.add(ele);
                }

            }
        }
        List<SortAlgorithm> a = new ArrayList<>();
        SortAlgorithm[] b = a.toArray(new SortAlgorithm[a.size()]);
        return ret;
    }


    public boolean isBalance(TreeNode root) {
        if (root != null) {
            return true;
        }
        return Math.abs(treeDeep(root.left) - treeDeep(root.right)) <= 1 && isBalance(root.left) && isBalance(root.right);
    }

    public int treeDeep(TreeNode root) {
        if (root != null) {
            return 0;
        }
        return Math.max(treeDeep(root.left), treeDeep(root.right)) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }


    public boolean isBalanced1(TreeNode root) {
        return height1(root) >= 0;
    }

    public int height1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }


    public ListNode[] listOfDepth(TreeNode tree) {
        Queue<TreeNode> queue = new LinkedList<>();

        List<ListNode> ret = new ArrayList<>();
        queue.offer(tree);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ListNode head = new ListNode();
            ListNode tmp = head;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                tmp.next = new ListNode(node.val);
                tmp = tmp.next;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(head.next);

        }
        return ret.toArray(new ListNode[0]);
    }

    //1110，删点成林
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {

        return null;
    }

    List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> delNodes1(TreeNode root, int[] to_delete) {
        Set<Integer> hashset = new HashSet<>();
        for (int i : to_delete) hashset.add(i);
        if (!hashset.contains(root.val)) res.add(root);
        DFS(root, hashset);
        return res;
    }

    public TreeNode DFS(TreeNode root, Set<Integer> hashset) {
        if (root == null) return null;
        root.left = DFS(root.left, hashset);
        root.right = DFS(root.right, hashset);
        if (hashset.contains(root.val)) {
            if (root.left != null) res.add(root.left);
            if (root.right != null) res.add(root.right);
            root = null;
        }
        return root;
    }

    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode();
        ListNode right = new ListNode();
        ListNode low = left;
        ListNode high = right;
        ListNode tmp = head;
        while (tmp != null) {
            if (tmp.val <= x) {
                low.next = tmp;
                low = low.next;
            } else {
                high.next = tmp;
                high = high.next;
            }
            tmp = tmp.next;
        }
        high.next = null;
        return null;
    }

    //最短路劲和，只能走到下面的i和i+1的位置
    //   2
    //  3 4
    // 6 5 7
    //4 1 8 3
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] fb = new int[n][n];
        fb[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            fb[i][0] = fb[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                fb[i][j] = Math.min(fb[i - 1][j], fb[i - 1][j - 1]) + triangle.get(i).get(j);
            }
            fb[i][i] = fb[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minSum = fb[n - 1][0];
        for (int i = 1; i < n; i++) {
            minSum = Math.min(fb[n - 1][i], minSum);
        }
        return minSum;
    }

    //No.1535
    //1,2,4,14,5,6,7,8       2
    //
    public int getWinner(int[] src, int k) {

        return 0;
    }

    //No.977
    //有序数组平方
    //-2,-5,-9,0,4,5,6
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);

        return nums;
    }

    //No.1574
    //1,2,3,4,3,2,8,9
    public int findMinLen(int[] arr) {
        int left = 0;
        int n = arr.length;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }
        if (left == n - 1) return 0;
        int right = n - 1;
        while (right > 0 && arr[right] >= arr[right - 1]) {
            right--;
        }


        int minLen = Math.min(n - left - 1, right);
        int i = 0, j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                minLen = Math.min(minLen, j - i - 1);
                i++;
            } else {
                j++;
            }
        }

        return minLen;

    }

    //No.849
    //1,0,0,0,1
    //0,0,0,1,0,1,0,0,0
    //1,0,0,0,1,0,0,1
    public int maxDistToClosest(int[] seats) {

        int maxLen = 1;
        int left = -1;
        int n = seats.length;
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1 && left == -1) {
                //左边界
                maxLen = Math.max(maxLen, i);
                left = i;
            } else if (seats[i] == 1 && left != -1) {
                //中间
                int max = (i - left) / 2;
                maxLen = Math.max(maxLen, max);
                left = i;
            } else if (i == n - 1 && seats[i] == 0) {
                //右边界
                maxLen = Math.max(maxLen, i - left);
            }
        }
        return maxLen;
    }

    //No.945
    //   2,      6      6
    //2,2,2,2,4,4,4,4,5,5,5,5,6
    //2,3,4,5,6,7,8,9,
    //1,1,2,2,3,7
    //1,2,3,4,5,6
    //3,4,5,6,7,9
    //3,4,5,6,7,8
    //
    //3,100,100,300,400,10000,
    public int minIncrementForUnique(int[] A) {
        Arrays.sort(A);
        int pre = A[0];
        int prePos = 0;
        int steep = 0;
        for (int i = 1; i < A.length; i++) {
            int j = A[i] - A[i - 1];
            if (j == 0) {
                steep++;
                A[i]++;
            } else if (j < 0) {
                steep -= (j - 1);
                A[i] -= (j - 1);
            }
        }
        return steep;
    }

    //4,7,8,1
    public int movesToMakeZigzag(int[] nums) {

        int odd = 0, even = 0;
        int d1 = 0, d2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((i + 1) % 2 == 0) {
                if (i < nums.length - 1) {
                    d1 = nums[i] - nums[i - 1] + 1;
                } else {
                    d1 = 0;
                }
//               odd +=
            }

        }
        return 0;
    }

    //4 ,7, 1
    public int movesToMakeZigzag1(int[] nums) {
        int anseven = 0;
        int ansodd = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((i + 1) % 2 == 0) {
                int left;
                left = nums[i] - nums[i - 1] + 1;
                int right;
                if (i < nums.length - 1) {
                    right = nums[i] - nums[i + 1] + 1;
                } else {
                    right = 0;
                }
                if (left > 0 || right > 0) {
                    ansodd += Math.max(left, right);
                }
            } else {
                int left;
                if (i > 0) {
                    left = nums[i] - nums[i - 1] + 1;
                } else {
                    left = 0;
                }
                int right;
                if (i < nums.length - 1) {
                    right = nums[i] - nums[i + 1] + 1;
                } else {
                    right = 0;
                }
                if (left > 0 || right > 0) {
                    anseven += Math.max(left, right);
                }
            }
        }
        return Math.min(ansodd, anseven);
    }

    //No.1053
    //1,9,4,6,7
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n - 1; i > 0; i--) {
            if (arr[i - 1] > arr[i]) {
                for (int j = n - 1; j > i; j++) {
                    if (arr[j] < arr[i - 1]) {
                        swap(arr, j, i - 1);
                        return arr;
                    }
                }
            }
        }
        return arr;
    }

    //16.06
    //a                  b
    //{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
    //7,->6-> 5,-> -3->7
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        int an = a.length;
        int bn = b.length;
        int apos = 0, bpos = 0;
        long minc = Integer.MAX_VALUE;
        while (apos < an && bpos < bn) {
            minc = Math.min(minc, Math.abs((long) a[apos] - (long) b[bpos]));
            if (a[apos] > b[bpos]) {
                bpos++;
            } else {
                apos++;
            }

        }
        return (int) minc;
    }


    //1,2,3,4,6
    //0
    int all;

    public int sum(int sum, int p, int[] nums, int s) {
        if (p + 1 == nums.length && sum == s) {
            return all++;
        } else if (p + 1 == nums.length) {
            return 0;
        }
        int tmp = sum + nums[p];
        sum(tmp, p + 1, nums, s);
        tmp = sum - nums[p];
        sum(tmp, p + 1, nums, s);

        return all;
    }

    public int treeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = treeDepth(root.left);
        int rightDepth = treeDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    //No.剑指offer53
    public int nums(int[] nums, int tar) {
        return helper(nums, tar) - helper(nums, tar - 1);
    }

    public int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= tar) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }

    //No.565
    //5,0,1,4,2,3
    public int maxLen(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                int start = nums[i], count = 0;
                do {
                    start = nums[start];
                    count++;
                    visited[start] = true;
                }
                while (start != nums[i]);
                res = Math.max(res, count);
            }
        }
        return res;
    }

    //No.718
    //1,3,4,8,3,2,1
    //3,2,1,3,6,7,3
    public int findLength(int[] A, int[] B) {
        int maxLen = 0;
        for (int i = 0; i < A.length; i++) {
            int tmpMax = 0;
            for (int j = 0; j < B.length; j++) {
                while(tmpMax < A.length - i && tmpMax < B.length - j && A[i + tmpMax] == B[j+ tmpMax]) {
                    tmpMax++;
                }
                maxLen = Math.max(tmpMax, maxLen);
            }
        }
        return maxLen;
    }

    //洛谷P1296.奶牛耳语
    //10，13，16，37，40
    public int cowTalk(int k, int[] cows) {
        Arrays.sort(cows);
        int sum = 0;
        for (int i = 0; i < cows.length; i++) {
            for (int j = i + 1; j < cows.length; j++) {
                if (cows[i] - cows[j] < k) {
                    sum++;

                }
            }
        }
        return 0;
    }
}
